package 动态规划;

/**
 * @Author: biubiu0002
 * @Date: 2021-07-11 13:17
 **/
public class 斐波那契数列 {
    public static void main(String[] args) {
        System.out.println(new 斐波那契数列().fibGundongShuzu(10));

    }

    public int fib(int n){
        int[] dp = new int[n+1];
        int i;
        if(n==0||n==1) return 0;
        dp[0]=0;
        dp[1]=1;

        for (i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[--i];

    }

    public int fibGundongShuzu(int n){
        if(n==0||n==1) return n;
        int p=0,q=1,r=1;
        for (int i=0;i<n;i++){
            p=q;
            q=r;
            r=p+q;
        }
        return p;


    }
}
